package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给出一个字符串s，分割s使得分割出的每一个子串都是回文串
 * 计算将字符串s分割成回文分割结果的最小切割数
 * 例如:给定字符串s="aab",
 * 返回1，因为回文分割结果["aa","b"]是切割一次生成的。
 * User:yxd
 * Date:2022-03-23
 * Time:22:30
 */
public class Dp8 {
    public int minCut (String s) {
        // write code here
        //状态定义F(i)分割i个字符串的最小分割次数
        //状态转移方程 F(i) 首先应该判断整个字符串是不是回文串然后在从前面到第i个字符每一个都遍历一下看其是否是字符串在做判断
        //初始F(0)= 0 F(1) = 1
        if(s == null || s.length() == 0){
            return -1;
        }
        int len = s.length();
        int[] dp = new int[len + 1];
        for(int i = 0;i <= len;i ++){
            dp[i] = i - 1;
        }
        for(int i = 1;i <= len;i ++){
            for(int j = 0;j < i;j ++){
                if(isPalindrome(s,j,i - 1)){
                    dp[i] = Math.min(dp[j] + 1,dp[i]);
                }
            }
        }
        return dp[len];
    }
    public boolean isPalindrome(String s,int start,int end){
        while(start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }
            start ++;
            end --;
        }
        return true;
    }
}
